package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。 
//
// 示例： 
//
// 输入： arr = [1,3,5,7,2,4,6,8], k = 4
//输出： [1,2,3,4]
// 
//
// 提示： 
//
// 
// 0 <= len(arr) <= 100000 
// 0 <= k <= min(100000, len(arr)) 
// 
// Related Topics 堆 排序 分治算法 
// 👍 53 👎 0


import own.stu.jobgib.playown.util.PrintUtil;

import java.util.PriorityQueue;

public class SmallestKLcci{
    public static void main(String[] args) {
        Solution solution = new SmallestKLcci().new Solution();
        PrintUtil.printArray(solution.smallestK(new int[]{1,3,5,7,2,4,6,8}, 4));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] smallestK(int[] arr, int k) {
            if (arr == null || arr.length <= 0 || arr.length < k) {
                return arr;
            }

            int[] ans = new int[k];
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
            for (int i : arr) {
                maxHeap.add(i);
                if (maxHeap.size() > k) {
                    maxHeap.poll();
                }
            }

            int i = 0;
            while (!maxHeap.isEmpty()) {
                ans[i++] = maxHeap.poll();
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
